#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int maxIncreasingSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        for (int i = 1; i < n; ++i)
        {
            if (nums[i] > nums[i - 1])
            {
                dp[i] = dp[i - 1] + 1;
            }
        }
        int ret = 1;
        for (int i = 0; i < n; ++i)
        {
            int n = dp[i];
            if (i - n >= 0 && dp[i - n] >= n)
                ret = max(ret, n);
            int t = n / 2;
            if (i - t >= 0 && dp[i - t] == n / 2)
                ret = max(ret, t);
        }
        return ret;
    }

    bool hasIncreasingSubarrays(vector<int>& nums, int k) {
        if (k == 1) return true;
        int n = nums.size();
        vector<int> dp(n, 1);
        int flag = 0;
        for (int i = 1; i < n; ++i)
        {
            if (i > flag && nums[i] > nums[i - 1])
            {
                dp[i] = dp[i - 1] + 1;
            }
        }
        for (int i = k; i < n; ++i)
        {
            if ((dp[i] == k || dp[i] == 2 * k) && dp[i - k] >= k)
                return true;
        }

        return false;
    }

    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        int ret = 1;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (nums[i] > nums[j])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
                ret = max(ret, dp[i]);
            }
        }
        return ret;
    }

    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> len(n, 1);
        vector<int> count(n, 1);
        int retlen = 1, retcount = 1;
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (nums[i] > nums[j])
                {
                    if (len[j] + 1 == len[i])
                    {
                        count[i] += count[j];
                    }
                    else if (len[j] + 1 > len[i])
                    {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }
            if (retlen < len[i])
            {
                retlen = len[i];
                retcount = count[i];
            }
            else if (retlen == len[i])
                retcount += count[i];
        }
        return retcount;
    }

    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        k = min(k, n / 2);
        vector<vector<int>> f(n, vector<int>(k + 1, -0x3f3f3f3f));
        vector<vector<int>> g(n, vector<int>(k + 1, -0x3f3f3f3f));
        f[0][0] = -prices[0], g[0][0] = 0;
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j <= k; ++j)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j >= 1)
                {
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        int ret = 0;
        for (int i = 0; i <= k; ++i)
        {
            ret = max(ret, g[n - 1][i]);
        }
        return ret;
    }
};